import java.util.ArrayList;
import java.util.List;

public class Test02 {
    int[] ret;  // 用于存储结果，每个元素右边比它小的元素个数
    int[] index;  // 记录元素在原始数组中的下标
    int[] indexTmp;  // 用于临时存储合并过程中的下标
    int[] tmp;  // 用于临时存储合并过程中的元素值

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ret = new int[n];  // 初始化结果数组
        index = new int[n];  // 初始化下标数组
        indexTmp = new int[n];  // 初始化临时下标数组
        tmp = new int[n];  // 初始化临时排序数组

        // 初始化 index 数组，记录每个元素的初始下标
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }

        // 开始归并排序
        mergeSort(nums, 0, n - 1);

        // 将结果数组转化为 List 形式输出
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            result.add(ret[i]);
        }
        return result;
    }

    // 归并排序算法
    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;

        int mid = (left + right) / 2;
        // 分治，递归处理左半部分和右半部分
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 合并两个有序的子数组
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                // 左边元素小于等于右边，不形成逆序对；大的元素放进tmp（降序归并）
                tmp[i] = nums[cur2];
                indexTmp[i++] = index[cur2++];
            } else {
                // 左边元素大于右边，形成逆序对
                ret[index[cur1]] += right - cur2 + 1;  // 更新逆序对的数量
                tmp[i] = nums[cur1];
                indexTmp[i++] = index[cur1++];
            }
        }
    }
}
